package com.origin.niuke.string;

/**
 * NC149 kmp算法
 * 算法：KMP
 * 减少了时间复杂度, 只需要指向模板串的指针回溯即可
 *
 * @author yezh
 * @date 2022/11/16 21:33
 */
public class NC149 {

    public int kmp(String S, String T) {
        int ans = 0, n = T.length(), m = S.length();
        int[] next = getNext(S);
        for (int i = 0, j = 0; i < n; i++) {
            // 走到这一步, 表示 S[0, j - 1] 与 T[i - j, i - 1] 是相等的
            while (j > 0 && T.charAt(i) != S.charAt(j))
                // 不相等, 就找 [0, j - 1] 的最大前缀长度
                j = next[j];
            if (T.charAt(i) == S.charAt(j)) ++j;
            if (j == m) {
                ++ans;
                // 获取 [0, m - 1] 的最大前缀长度
                j = next[j - 1];
            }
        }
        return ans;
    }

    /**
     * 获取 next 数组
     * 神奇的地方在于前缀是从 0 开始的,
     * j 可以表示前缀字符的个数,
     * 也可以表示当 s[m] 与 t[n] 不相同时, n 下一个回溯的位置
     *
     * @param s 模板串
     * @return next 数组
     */
    int[] getNext(String s) {
        int len = s.length();
        // 表示 [0, i] 的最大前后缀长度
        int[] next = new int[len];
        for (int i = 1, j = 0; i < len; i++) {
            // 当前的 j 表示 [0, i - 1] 的最长前后缀
            while (j > 0 && s.charAt(i) != s.charAt(j))
                // 走到这一步, 表示 [0, j - 1] 和 [i - j, i - 1] 是相等的
                // 不相等, 就找 [0, j - 1] 的最长前后缀长度
                // 因为 j 是长度, 所以当 j 表示下标时, 就会指向最长前缀的后一个字符, 而这个字符就是下次要比较的位置
                j = next[j - 1];
            if (s.charAt(i) == s.charAt(j)) ++j;
            // j 表示长度, 不要把 j 想成下标, 这样好思考点, 如果 s.charAt(0) 和 s.charAt(i) 相等,
            // 那么 [0, i] 的最大前后缀的长度是 1, 也就是 0 + 1
            // 而 +1 后的 j 就是下一个要比较是否相等的字符
            next[i] = j;
        }
        return next;
    }

}
